剑指Offer 6 重建二叉树

##　题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

对于前序遍历，它的第一个元素就是根节点；
对于中序遍历，根节点左面是左子树，右面是右子树；
通过递归不断地分割，对每一个节点赋值；

代码

我十分愚蠢的代码：

public class Solution {
    public  TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            if (pre==null||in==null)
            {
                return null;
            }
           TreeNode root = test(pre,in);
            root.toString();
            return root;
        }
        public TreeNode test( int pre[],int in[] )
        {
            TreeNode treeNode1 = new TreeNode(pre[0]);
            int a[] = new  int[pre.length];
            int b[] = new  int[pre.length];
            int flag=0;
            for (int i = 0 ; i<in.length;i++)
            {
                if (in[i] == pre[0])
                {
                    flag=i;
                    break;
                }
            }
            if (flag!=0) {
                int left[] = new int[flag];
                System.arraycopy(in, 0, left, 0, flag);
                int leftpre[] = new int[flag];
                System.arraycopy(pre, 1, leftpre, 0, flag);
                treeNode1.left = test(leftpre,left);
            }
            if (flag!=pre.length-1) {
                int right[] = new int[pre.length-flag-1];
                System.arraycopy(in, flag+1,right, 0, in.length-(flag+1));
                int rightpre[] = new int[pre.length-flag-1];
                System.arraycopy(pre, flag+1, rightpre, 0, in.length-(flag+1));
                treeNode1.right =  test(rightpre,right);
            }
            return treeNode1;
        }
}

收获

就像上面的代码，我新建了一个函数，但是却没考虑太多，参数是数组，这样造成了我需要大量的新数组，而假定我传参是“指针”，就是说原序列的位置，这样就只需要在原序列操作；

递归
我们可以看到，整个函数的构造是这样的

public TreeNode test( int pre[],int in[] )
{
    if (flag!=0) {                       //递归
        treeNode1.left = test(leftpre,left);
    }
    if (flag!=pre.length-1) {            //递归
        treeNode1.right =  test(rightpre,right);
    }
    
    return treeNode1;
}

其实有递归和分治的想法；以一个if作为递归的结束，然后不断地返回值，最后建立好一座二叉树，是不是很厉害呢；

2017-03-19